__author__ = 'st316'
'''
Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
'''


#Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def toString(self):
        cur = self
        s = ''
        while cur.next:
            s += str(cur.val) + ' -> '
            cur = cur.next
        return s + str(cur.val)


class Solution:
    # @return a ListNode
    def removeNthFromEnd(self, head, n):
        p = head
        q = head
        pq = None
        i = n
        while i > 0:
            p = p.next
            i -= 1
        while p:
            p = p.next
            pq = q
            q = q.next
        if pq:
            pq.next = q.next
        else:
            head = q.next
        return head


if __name__ == '__main__':
    l = [1, 2, 3, 4, 5]
    ll = ListNode(l[0])
    cur = ll
    for v in l[1:]:
        cur.next = ListNode(v)
        cur = cur.next

    s = Solution()
    print s.removeNthFromEnd(ll, 5).toString()
